package leetcode_200;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *PalindromePartitioning_131 判断一个字符串可被分割成多少个回文字符串  把所有可能存入集合
 *describe:用数组记录所有回文字符串 深度优先搜索遍历整个数组 AC 81%
 *2018年5月29日 下午7:48:11
 */
public class PalindromePartitioning_131_ {
	List<List<String>> res;
	boolean dp[][];
	String s;
	public static void main(String[] args) {
		PalindromePartitioning_131_ test=new PalindromePartitioning_131_();
		test.partition("aab");

	}
	
	public List<List<String>> partition(String s) {
        dp=new boolean [s.length()][s.length()];
        this.s=s;
        this.res=new ArrayList<List<String>>();
        for(int i=0;i<dp.length;++i)
        	for(int j=i;j<dp.length;++j) {
        		if(isPalindrome(s.substring(i, j+1)))
        			dp[i][j]=true;
        	}
        help(new ArrayList<String>(),0);
		return this.res;
    }
	
	public void help(List<String> list,int index) {
		for(int i=index;i<dp.length;++i) {
			if(dp[index][i]) {
				list.add(s.substring(index,i+1));
				if(i==dp.length-1) {
					List<String> now=new ArrayList<String>();
					now.addAll(list);
					this.res.add(now);
				}
				help(list,i+1);
				list.remove(list.size()-1);
			}
		}
	}
	
	private boolean isPalindrome(String s) {
		int i=0,j=s.length()-1;
		while(i<j) {
			if(s.charAt(i)!=s.charAt(j))
				return false;
			++i;
			--j;
		}
		return true;
	}

}
